package 算法基础模板.chapter_03.搜索;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author Summerday
 */
class Solution {
    public List<List<Integer>> list = new LinkedList<>();
    public int[][] obstacleGrid;
    public boolean[][] vistis;

    public List<List<Integer>> pathWithObstacles (int[][] obstacleGrid) {
        this.obstacleGrid = obstacleGrid;
        this.vistis = new boolean[obstacleGrid.length][obstacleGrid[0].length];
        LinkedList<List<Integer>> cur = new LinkedList<>();
        List<Integer> point = new ArrayList<>();
        point.add(0);
        point.add(0);
        cur.add(point);
        if (obstacleGrid[0][0] == 1) {
            return list;
        }
        pathWithObstacles(0, 0, cur);
        return list;
    }

    public boolean pathWithObstacles (int x, int y, LinkedList<List<Integer>> cur) {
        if (x == obstacleGrid.length - 1 && y == obstacleGrid[0].length - 1) {
            list = new LinkedList<>(cur);
            return true;
        }
        // 剪枝
        if (vistis[x][y]) {
            return false;
        }
        vistis[x][y] = true;
        if (valid(x + 1, y)) {
            List<Integer> point = new ArrayList<>();
            point.add(x + 1);
            point.add(y);
            cur.add(point);
            if (pathWithObstacles(x + 1, y, cur)) {
                return true;
            }
            cur.removeLast();
        }
        if (valid(x, y + 1)) {
            List<Integer> point = new ArrayList<>();
            point.add(x);
            point.add(y + 1);
            cur.add(point);
            if (pathWithObstacles(x, y + 1, cur)) {
                return true;
            }
            cur.removeLast();
        }
        return false;
    }

    public boolean valid (int x, int y) {
        return x >= 0 && y >= 0 && x < obstacleGrid.length && y < obstacleGrid[0].length && obstacleGrid[x][y] != 1;
    }
}

